#include "maze.h"

#include <QPoint>
#include <QRandomGenerator>
#include <QStack>

Maze::Maze( int w, int h )
{
    walls.resize( w );
    for ( auto& r : walls )
    {
        r.resize( h );
        r.fill( true );
    }

    generateMaze( 1, 1 );

    // 设置出口
    editX               = w - 2;
    editY               = h - 2;
    walls[editX][editY] = false;
}

bool Maze::isWall( int x, int y ) const
{
    if ( x < 0 || x >= walls.size() || y < 0 || y >= walls[0].size() )
    {
        return true;
    }
    return walls[x][y];
}

bool Maze::isExit( int x, int y ) const
{
    return x == editX && y == editY;
}

int Maze::getWidth() const
{
    return walls.size();
}

int Maze::getHeight() const
{
    return walls.isEmpty() ? 0 : walls[0].size();
}

void Maze::generateMaze( int x, int y )
{
    // 生成仍有瑕疵，有时会有无解迷宫
    QStack<QPoint> stack;
    stack.push( QPoint( x, y ) );
    walls[x][y] = false;

    while ( !stack.isEmpty() )
    {
        QPoint          curr      = stack.top();
        QVector<QPoint> neighbors = getNeighbors( curr.x(), curr.y() );

        if ( neighbors.isEmpty() )
        {
            stack.pop();
        }
        else
        {
            int    randomindex        = QRandomGenerator::global()->bounded( neighbors.size() );
            QPoint next               = neighbors[randomindex];
            int    wallx              = ( curr.x() + next.x() ) / 2;
            int    wally              = ( curr.y() + next.y() ) / 2;
            walls[wallx][wally]       = false;
            walls[next.x()][next.y()] = false;
            stack.push( next );
        }
    }
}

QVector<QPoint> Maze::getNeighbors( int x, int y )
{
    QVector<QPoint> neighbors;
    QVector<QPoint> directions = { QPoint( -2, 0 ), QPoint( 2, 0 ), QPoint( 0, -2 ), QPoint( 0, 2 ) };
    for ( const QPoint& dir : directions )
    {
        int newx = x + dir.x();
        int newy = y + dir.y();
        if ( newx >= 1 && newx < walls.size() - 1 && newy >= 1 && newy < walls[0].size() - 1 && walls[newx][newy] )
        {
            neighbors.append( QPoint( newx, newy ) );
        }
    }
    return neighbors;
}
